package 动态规划算法;

public class testKnapsack2 {

    int[] vs = {0, 2, 4, 3, 7};
    int[] ws = {0, 2, 3, 5, 5};
    Integer[][] results = new Integer[5][11];

    private int ks2(int i, int c) {
        int result = 0;
        // 如果该结果已经被计算，那么直接返回
        if (results[i][c] != null) {
            return results[i][c];
        }
        if (i == 0 || c == 0) {
            // 初始条件
            result = 0;
        } else if (ws[i] > c) {
            // 装不下该珠宝
            result = ks2(i - 1, c);
        } else {
            // 可以装下
            int tmp1 = ks2(i - 1, c);
            int tmp2 = ks2(i - 1, c - ws[i]) + vs[i];
            result = Math.max(tmp1, tmp2);
        }
        results[i][c] = result;
        return result;
    }

    public void testKnapsack2() {
        int result = ks2(4, 10);
        System.out.println(result);
    }
}
